package com.wc.acwing.基础算法.位运算.a乘b;

import java.util.Scanner;

/**
 * @Author congge
 * @Date 2024/1/16 1:03
 * @description 64位整数乘法
 */
public class Main {
    static long a, b, p;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        a = sc.nextLong();
        b = sc.nextLong();
        p = sc.nextLong();
        System.out.println(mul(a, b, p));
    }

    // 快速乘
    // 将b转换为2进制思想进行乘
    static long mul(long a, long b, long p) {
        long res = 0;
        while (b > 0) {
            if ((b & 1) == 1) {
                res = (res + a) % p;
            }
            b >>= 1;
            a = 2 * a % p;
        }
        return res;
    }
}
